The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.

Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. An optimal parallel algorithm for finding a spanning tree on the trapezoid graph is given by Bera et al., it takes O(log n) time with O(n/log n) processors on the EREW (Exclusive-Read Exclusive-Write) PRAM. Bera et al.'s algorithm is very simple and elegant. Moreover, it can correctly construct a spanning tree when the graph is connected. However, their algorithm can not accept a disconnected graph as an input. Applying their algorithm to a disconnected graph, Concurrent-Write occurs once for each connected component, thus this can not be achieved on EREW PRAM. In this paper we present an O(log n) time parallel algorithm with O(n/log n) processors for constructing a spanning forest on trapezoid graph G on EREW PRAM even if G is a disconnected graph.

This paper deals with the Optimum Communication Spanning Tree Problem (OCST) which is well known as an NP-hard problem. For solving the problem, we uses an evolutionary approach. This paper presents a new effective tree encoding and proposes a tree construction routine (TCR) to generate a tree from the encoding. The basic principle is to break a cycle. We also propose a new crossover operator that focuses on the inheritance of parental information and the use of network information. Consequently, we confirm that the proposed algorithm is superior to other algorithms applied to the OCST problem or other tree problems. Moreover, our method can find a better solution than the solution which was previously known as the best solution. In addition, we analyzed the locality and diversity property of encoding and observed that the proposed method has high locality and at the same time it preserves population diversity for many generations. Finally, we conclude that these properties are the main reasons why the proposed method outperforms the other encodings.

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.

Genetic Algorithm (GA) and other Evolutionary Algorithms (EAs) have been successfully applied to solve constrained minimum spanning tree (MST) problems of the communication network design and also have been used extensively in a wide variety of communication network design problems. Choosing an appropriate representation of candidate solutions to the problem is the essential issue for applying GAs to solve real world network design problems, since the encoding and the interaction of the encoding with the crossover and mutation operators have strongly influence on the success of GAs. In this paper, we investigate a new encoding crossover and mutation operators on the performance of GAs to design of minimum spanning tree problem. Based on the performance analysis of these encoding methods in GAs, we improve predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. The proposed crossover and mutation operators offer locality, heritability, and computational efficiency. We compare with the approach to others that encode candidate spanning trees via the Pr?fer number-based encoding, edge set-based encoding, and demonstrate better results on larger instances for the communication spanning tree design problems.

In this paper, authors present new schemes of our proposed Global Open Ethernet (GOE) technology from a viewpoint of improving reliability in metro-area Ethernet environment and show the numerical evidence on their performance results. Although several standardized or vendor proprietary technologies are proposed to improve Ethernet reliability, they still have reliability problems in terms of long failure recovery time (due to forwarding database (FDB) flush and recovery from a root bridge failure on spanning tree protocol), broadcast storm, and packet loss in network reconfiguration. To solve these problems, we introduce three schemes, a Per Destination - Multiple Rapid Spanning Tree Protocol (PD-MRSTP), a GOE Virtual Switch Redundancy Protocol (GVSRP), and an In-Service Reconfiguration (ISR) schemes. PD-MRSTP scheme reduces the failure recovery time by eliminating the need to flush the FDB and to recover from root bridge failures. GVSRP scheme ensures the reliability of connections between a GOE domain and a legacy Ethernet domain. Combined with PD-MRSTP, GVSRP prevents broadcast storm problems due to loops in the inter-domain area. ISR scheme enables in-service bridge replacement and upgrade without packet loss. Evaluating our prototype system, we obtained the following remarkable performance results. The GOE network using PD-MRSTP scheme delivered a fast failure recovery performance (4 ms) independent of the number of MAC address entries, whereas the legacy Ethernet network took 522 ms when a bridge had 6000 MAC address entries. Since we found that the failure recovery time increased in proportion to the number of MAC address entries, the one in large carrier network having one million of MAC address entries would take several tens of seconds. Thus using PD-MRSTP can reduce failure recovery time one ten-thousandth comparing with that of legacy Ethernet. In addition, evaluation of the ISR scheme demonstrated that a network can be upgraded with zero packet loss. Therefore, a GOE-based VPN is a promising alternative to other Ethernet VPNs for its reliability and stability.

We consider the problem of computing the optimal swap edges of a shortest-path tree. This problem arises in designing systems that offer point-of-failure shortest-path rerouting service in presence of a single link failure: if the shortest path is not affected by the failed link, then the message will be delivered through that path; otherwise, the system will guarantee that, when the message reaches the node where the failure has occurred, the message will then be re-routed through the shortest detour to its destination. There exist highly efficient serial solutions for the problem, but unfortunately because of the structures they use, there is no known (nor foreseeable) efficient distributed implementation for them. A distributed protocol exists only for finding swap edges, not necessarily optimal ones. We present two simple and efficient distributed algorithms for computing the optimal swap edges of a shortest-path tree. One algorithm uses messages containing a constant amount of information, while the other is tailored for systems that allow long messages. The amount of data transferred by the protocols is the same and depends on the structure of the shortest-path spanning-tree; it is no more, and sometimes significantly less, than the cost of constructing the shortest-path tree.

Automatic discovery of physical topology plays a crucial role in enhancing the manageability of modern large Ethernet mesh networks. Despite the importance of the problem, earlier research and commercial network management tools have typically concentrated on either discovering active topology, or proprietary solutions targeting specific product families. Recent works [1]-[3] have demonstrated that physical topology can be determined using standard SNMP MIB, but these algorithms depend on Filtering Database and rely on the so-called spanning tree protocol (IEEE 802.1d) in order to break cycles, thereby avoiding the possibility of infinitely circulating packets and deadlocks. A previous work [1] requires that Filtering Database entries are completed; however it is a very critical assumption in a realistic Ethernet mesh network. In this paper, we have proposed a new topology discovery algorithm which works without the complete knowledge of Filtering Database. Our algorithm can discover complete physical topology including inactive interfaces eliminated by the spanning tree protocol in LEMNs. The effectiveness of the algorithm is demonstrated by an implementation.

A novel evolutionary algorithm is described for designing the topology of spanning tree-based communication networks. Two specific performance objectives are dealt with: the optimum communication spanning tree problem (OCSTP), and the quadratic minimum spanning tree problem (q-MST). Improved network performance is reliably obtained when using the proposed algorithm on accepted benchmark instances, in comparison with the previous best-known approaches. The same methodology can be applied straightforwardly to the design of communication networks with other objectives.

This paper deals with minimum spanning tree problems where each edge weight is a fuzzy random variable. In order to consider the imprecise nature of the decision maker's judgment, a fuzzy goal for the objective function is introduced. A novel decision making model is constructed based on possibility theory and on a stochastic programming model. It is shown that the problem including both randomness and fuzziness is reduced to a deterministic equivalent problem. Finally, a polynomial-time algorithm is provided to solve the problem.

One of the important problems in overlay multicast is how to deal with node failures and ungraceful leavings. When a non-leaf end host fails or leaves the multicast session, all downstream nodes will be affected. In this paper, we adopt the proactive approach, which pre-calculates a candidate node (called parent-to-be) for each node to connect to in case its current parent dies. The goal is to recover the overlay multicast tree quickly so that the disruption of service to those affected nodes is minimized. We combine the local parent-to-be locating and global parent-to-be locating schemes together, in order to take advantage of less interference in the local scheme and the flexibility of the global scheme. The quality of the recovered tree is improved while the responsiveness of the proactive approach is maintained.

Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence Nn-1,Nn,...,Nm is #P-complete (see e.g.,[3]), where Ni denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence Nn-1,Nn,...,Nm, we show an interesting and stronger property that the sequence γn-1,γn,...,γm, where γi denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence Nn-1,Nn,...,Nm.

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.

A problem of obtaining an optimal file transfer of a file transmission net N is to consider how to transmit, with the minimum total cost, copies of a certain file of information from some vertices, called sources, to other vertices of N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net N. Some classes of N, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed, are known. In the characterization, we assumed that file given originally to the source remains at the source without being transmitted. In this paper, we relax the assumption to the one that a sufficient number of copies of the file are given to the source and those copies can be transmitted from the source to other vertices on N. Under this new assumption, we characterize a class of file transmission nets, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed. A minimum spanning tree with degree constraints plays a key role in the algorithm.

Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.

Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.

This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

The use of Internet for various business applications and resource sharing has grown tremendously over the last few years. Internet security has become an important issue for both academic and industrial sectors. Much related network security research has been conducted such as user authentication, data confidentiality, and data integrity. In some applications, a critical document can be divided into pieces and allocated in different locations over the Internet for security access concern. To access such an important document, one must reconstruct the divided pieces from different locations under the given Internet environment. In this paper, a probability model for reconstructing secret sharing and algorithms to perform share assignment are presented. Also, an evaluation algorithm to measure the probability of secret sharing reconstruction is proposed. Illustrative examples and simulation results are provided to demonstrate the applicability of our method.

In this paper, we present a new approach which is spanning tree-based genetic algorithm for solving a multi-objective transportation problem. The transportation problem as a special type of the network optimization problems has the special data structure in solution characterized as a transportation graph. In encoding transportation problem, we introduce one of node encodings based on a spanning tree which is adopted as it is capable of equally and uniquely representing all possible basic solutions. The crossover and mutation were designed based on this encoding. Also we designed the criterion that chromosome has always feasibility converted to a transportation tree. In the evolutionary process, the mixed strategy with (µ+λ)-selection and roulette wheel selection is used. Numerical experiments show the effectiveness and efficiency of the proposed algorithm.

Let T1, , Tn be n spanning trees rooted at node r of graph G. If for any node v, n paths from r to v, each path in each spanning tree of T1, , Tn, are internally disjoint, then T1, , Tn are said to be independent spanning trees rooted at r. A graph G is called an n-channel graph if G has n independent spanning trees rooted at each node of G. We generalize the definition of n-channel graphs. If for any node v of G, among the n paths from r to v, each path in each spanning tree of T1, , Tn, there are k internally disjoint paths, then T1, , Tn are said to be (k,n)-independent spanning trees rooted at r of G. A graph G is called a (k,n)-channel graph if G has (k,n)-independent spanning trees rooted at each node of G. We study two fault-tolerant communication tasks in (k,n)-channel graphs. The first task is reliable broadcasting. We analyze the relation between the reliability and the efficiency of broadcasting in (k,n)-channel graphs. The second task is secure message distribution such that one node called the distributor attempts to send different messages safely to different nodes. We should keep each message secret from the nodes called adversaries. We give two message distribution schemes in (k,n)-channel graphs. The first scheme uses secret sharing, and it can tolerate up to t+k-n listening adversaries for any t < n if G is a (k,n)-channel graph. The second scheme uses unverifiable secret sharing, and it can tolerate up to t+k-n disrupting adversaries for any t < n/3 if G is a (k,n)-channel graph.